class Heap {
  constructor(compare) {
    this.heap = [];
    this.compare = compare;
  }
  size() {
    return this.heap.length;
  }
  isEmpty() {
    return this.heap.length === 0;
  }
  peek() {
    return this.heap[0] ?? undefined;
  }
  push(value) {
    this.heap.push(value);
    this.bubbleUp(this.heap.length - 1);
  }
  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.compare(this.heap[index], this.heap[parentIndex]) < 0) {
        [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
        index = parentIndex;
      } else break;
    }
  }
  pop() {
    if (this.isEmpty()) return undefined;
    const top = this.heap[0];
    const last = this.heap.pop();
    if (!this.isEmpty()) {
      this.heap[0] = last;
      this.sinkDown(0);
    }
    return top;
  }
  sinkDown(index) {
    let current = index;
    const length = this.size();
    while (true) {
      const left = 2 * current + 1;
      const right = 2 * current + 2;
      let target = current;
      if (left < length && this.compare(this.heap[left], this.heap[target]) < 0)
        target = left;
      if (right < length && this.compare(this.heap[right], this.heap[target]) < 0)
        target = right;
      if (target !== current) {
        [this.heap[current], this.heap[target]] = [this.heap[target], this.heap[current]];
        current = target;
      } else break;
    }
  }
  update(oldValue, newValue) {
    const index = this.heap.indexOf(oldValue);
    if (index === -1) return false;
    this.heap[index] = newValue;
    this.bubbleUp(index);
    this.sinkDown(index);
    return true;
  }
  remove(value) {
    const index = this.heap.indexOf(value);
    if (index === -1) return false;
    const last = this.heap.pop();
    if (index === this.heap.length) return true;
    this.heap[index] = last;
    this.bubbleUp(index);
    this.sinkDown(index);
    return true;
  }
  contains(value) {
    return this.heap.includes(value);
  }
}

class Prim {
  // 核心数据结构，存储「横切边」的优先级队列
  constructor(graph) {
    this.graph = graph;
    this.pq = new Heap((a, b) => a[2] - b[2]);
    // 类似 visited 数组的作用，记录哪些节点已经成为最小生成树的一部分
    this.inMST = new Array(graph.length).fill(false);
    // 记录最小生成树的权重和
    this._weightSum = 0;

    // 随便从一个点开始切分都可以，我们不妨从节点 0 开始
    this.inMST[0] = true;
    this.cut(0);

    // 不断进行切分，向最小生成树中添加边
    while (!this.pq.isEmpty()) {
      const edge = this.pq.pop();
      const to = edge[1];
      const weight = edge[2];
      if (this.inMST[to]) {
        // 节点 to 已经在最小生成树中，跳过
        // 否则这条边会产生环
        continue;
      }
      // 将边 edge 加入最小生成树
      this._weightSum += weight;
      this.inMST[to] = true;
      // 节点 to 加入后，进行新一轮切分，会产生更多横切边
      this.cut(to);
    }
  }

  // 将 s 的横切边加入优先队列
  cut(s) {
    // 遍历 s 的邻边
    for (const edge of this.graph[s]) {
      const to = edge[1];
      if (this.inMST[to]) {
        // 相邻接点 to 已经在最小生成树中，跳过
        // 否则这条边会产生环
        continue;
      }
      // 加入横切边队列
      this.pq.push(edge);
    }
  }

  // 最小生成树的权重和
  weightSum() {
    return this._weightSum;
  }

  // 判断最小生成树是否包含图中的所有节点
  allConnected() {
    return this.inMST.every(Boolean);
  }
};

// test
const graph = [
  [[0, 1, 1], [0, 2, 2]],
  [[1, 0, 1], [1, 2, 3], [1, 3, 4]],
  [[2, 0, 2], [2, 1, 3], [2, 3, 5]],
  [[3, 1, 4], [3, 2, 5]],
];
const prim = new Prim(graph);
console.log(prim.weightSum()); // 7
console.log(prim.allConnected()); // true

